package arr_sum

func LongestLessSumSubArrayLength(arr []int, K int) int {
	N := len(arr)
	minSumArr := make([]int, N)
	minSumEnd := make([]int, N)
	minSumArr[N-1] = arr[N-1]
	minSumEnd[N-1] = N-1
	for i:=N-2; i>=0; i-- {
		if minSumArr[i+1] <= 0 {
			minSumArr[i] = arr[i] + minSumArr[i+1]
			minSumEnd[i] = minSumEnd[i+1]
		} else {
			minSumArr[i] = arr[i]
			minSumEnd[i] = i
		}
	}
	end := 0
	sum := 0
	ans := 0
	for i:=0; i<len(arr); i++ {
		for end < len(arr) && sum + minSumArr[end] <= K {
			sum += minSumArr[end]
			end = minSumEnd[end] + 1
		}
		ans = Max(ans, end-i)
		if end > i {
			sum -= arr[i]
		} else {
			end = i+1
		}
	}
	return ans
}
